//bool solve(string A, string B) {
//    if (A.size() != B.size()) return false;
//    return (A + A).find(B) != string::npos;
//}



//class Solution {
//public:
//    class Compare
//    {
//    public:
//        bool operator()(ListNode* l1, ListNode* l2)
//        {
//            return l1->val > l2->val;
//        }
//    };
//    ListNode* mergeKLists(vector<ListNode*>& lists) {
//        ListNode* newhead = new ListNode(0);
//        ListNode* prev = newhead;
//        priority_queue<ListNode*, vector<ListNode*>, Compare> heap;
//        for (auto head : lists)
//        {
//            if (head != nullptr)
//                heap.push(head);
//        }
//        while (heap.size())
//        {
//            ListNode* cur = heap.top();
//            heap.pop();
//            prev->next = cur; prev = cur;
//            if (cur->next)
//                heap.push(cur->next);
//        }
//
//        prev = newhead->next;
//        delete newhead;
//        return prev;
//    }
//};




//#include <iostream>
//using namespace std;
//const int N = 110;
//int n, m;
//int arr[N][N];
//int dp[N][N];
//int dx[4] = { 0, 0, 1, -1 };
//int dy[4] = { 1, -1, 0, 0 };
//int dfs(int i, int j)
//{
//	if (dp[i][j]) return dp[i][j];
//	int len = 1;
//	for (int k = 0; k < 4; k++)
//	{
//		int x = i + dx[k], y = j + dy[k];
//		if (x >= 1 && x <= n && y >= 1 && y <= m && arr[x][y] < arr[i][j])
//		{
//			len = max(len, 1 + dfs(x, y));
//		}
//	}
//	dp[i][j] = len;
//	return len;
//}
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cin >> arr[i][j];
//		}
//	}
//	int ret = 1;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			ret = max(ret, dfs(i, j));
//		}
//	}
//	cout << ret << endl;
//	return 0;
//}


//#include <iostream>
//#include <string>
//#include <algorithm>
//using namespace std;
//const int N = 1e5 + 10;
//pair<int, string> sp[N];
//int main()
//{
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> sp[i].second >> sp[i].first;
//	}
//	sort(sp, sp + n);
//	for (int i = 0; i < n; i++)
//	{
//		cout << sp[i].second << endl;
//	}
//	return 0;
//}



